W16. Amortized Analysis

Author

Nikolai Kudasov

Published

May 5, 2026

1. Theory

1.1 Why Amortized Analysis Is Needed
1.1.1 Cost of a Sequence

Many data structures have operations whose individual worst-case costs look scary, even though long valid sequences of operations are cheap overall. Amortized analysis is the method used to explain this situation rigorously.

The key idea is to analyze a sequence of operations, not a single operation in isolation. A single operation may cost , but if such expensive operations cannot happen too often, then the average cost per operation over every valid sequence may still be or .

This is a worst-case guarantee over sequences. It is not the same as probabilistic average-case analysis. Average-case analysis assumes a probability distribution over inputs or operation choices. Amortized analysis makes no such assumption: it says that every legal sequence of operations has total cost at most some bound .

1.1.2 Stack with Multi-Pop

Consider a stack supporting three operations:

  • pushes value onto the stack;
  • removes the top value;
  • removes up to the top values.

The worst-case cost of one is , and the worst-case cost of one is . A single can cost , and if the stack currently contains elements, this can be .

A naive worst-case-per-operation argument would say that operations may cost , because each operation might be treated as if it could cost . This is too pessimistic. Every element popped by or must first have been pushed. Since at most pushes can occur in a sequence of operations, at most elements can be popped in total. Therefore the whole sequence costs , not .

This example captures the spirit of amortized analysis: expensive operations spend work that was made possible by earlier cheap operations.

1.2 Aggregate Analysis
1.2.1 Method

Aggregate analysis is the simplest amortized-analysis technique. Instead of assigning different charges to different operation types, it directly bounds the total running time of any sequence of operations.

The method has two steps:

  1. Prove that every valid sequence of operations has total actual cost at most .
  2. Divide by to obtain an amortized cost per operation:

The symbol denotes amortized cost. It does not mean the actual cost of every operation is equal to . It means that, over the whole sequence, the operations can be charged as if each cost at most on average.

Aggregate analysis is easy to understand, but it can be too coarse. It gives one common amortized bound for all operations, even when different operation types have different natural costs.

1.2.2 Binary Counter

A standard example is a binary counter stored as a bit array , where is the least significant bit.

INCREMENT(A, k)
1  i = 0
2  while i < k and A[i] == 1
3      A[i] = 0
4      i = i + 1
5  if i < k
6      A[i] = 1

One increment may flip many bits. For example, becomes , which flips four bits. Thus a single operation can cost .

However, over many increments, low-order bits flip much more often than high-order bits. Bit flips every increment, bit flips every two increments, bit flips every four increments, and so on. For increments, the total number of bit flips is bounded by

So the total cost of increments is , and the amortized cost of one increment is , even though one individual increment may flip bits.

1.3 Accounting Method
1.3.1 Credits

The accounting method assigns each operation an amortized cost , which may differ from its actual cost .

If , the operation stores the difference as credit. If , the operation spends previously stored credit. The charging scheme is valid only if the credit balance never becomes negative.

Formally, for every prefix of the operation sequence,

for all . This prefix condition is essential. It prevents the analysis from borrowing credit from future operations that have not happened yet.

1.3.2 Stack Credits

For the stack with , , and , a valid accounting scheme is:

Operation Actual cost Amortized cost
number of removed elements

Each push pays for itself and stores credit on the pushed element. Later, when that element is removed by either or , its stored credit pays for the removal. Since an element cannot be popped more than once, the credit is sufficient.

This proves amortized cost per stack operation.

1.3.3 Binary Counter Credits

For the binary counter, charge for every change from to , and charge for every change from to .

When a bit changes from to , one unit pays for the actual flip and one unit is stored as credit on that bit. Later, when that same bit changes from to , the stored credit pays for the flip. Every trailing that becomes already has its own credit.

An increment changes at most one bit from to , so it receives amortized cost at most . Therefore binary-counter increment has amortized cost.

1.4 Potential Method
1.4.1 Potential Functions

The potential method is a mathematical version of the accounting method. Instead of placing explicit credits on individual objects, it defines a nonnegative stored energy for the whole data structure.

Let be the state of the data structure after the -th operation. A potential function maps states to real numbers. The amortized cost of operation is

If the potential increases, the operation is charged extra and stores energy for the future. If the potential decreases, the operation uses stored energy to pay for actual work.

To make the bound valid, the potential must satisfy

for every . Usually and . Then summing the amortized costs telescopes:

So the total amortized cost upper-bounds the total actual cost.

1.4.2 Stack Potential

For the stack, choose

This potential is always nonnegative. A push costs and increases potential by , so its amortized cost is . A pop costs and decreases potential by , so its amortized cost is . A operation removing elements costs and decreases potential by , so its amortized cost is also .

This is the same intuition as the accounting method: each stack element represents one unit of stored future removal work.

1.4.3 Binary Counter Potential

For the binary counter, choose

Suppose an increment changes trailing bits to and then changes one bit to . The actual cost is . The number of bits decreases by and increases by , so the potential change is .

Therefore

Again the amortized cost is constant. Long carry chains are paid for by the potential stored in the trailing bits.

1.5 Dynamic Tables
1.5.1 Expansion Only

A dynamic array stores elements in a contiguous table with some capacity and current number of elements . The operation appends one element. If the table is full, the data structure allocates a new table of double capacity and copies all existing elements.

A single append may cost during resizing, but resizing happens only after many cheap appends. One potential function for expansion-only dynamic arrays is

This potential is useful when the table is at least half full after initialization and resizing. It grows by on ordinary appends, storing credit for the next copy. When a resize happens, capacity doubles, and the drop in potential pays for copying the old elements.

The result is amortized time per .

1.5.2 Expansion and Contraction

If the table also supports , contraction must be handled carefully. A bad rule such as “halve the table whenever it becomes half full” can cause repeated grow-shrink oscillation. The standard fix is hysteresis: grow when full, but shrink only when the load drops below one quarter.

The load factor is

With doubling at and halving below , the table has a buffer zone around half full. A suitable potential is

The potential is zero near and grows when the table becomes either too full or too empty. That stored potential pays for the next expansion or contraction. With this choice, both and have amortized cost.

1.6 More Amortized Data Structures
1.6.1 Queue from Two Stacks

A queue can be implemented using two stacks. Let be the stack used for enqueues and be the stack used for dequeues.

  • pushes onto .
  • pops from if is nonempty.
  • If is empty, move all elements from to by popping them from and pushing them onto , then pop from .

The transfer reverses the order, so the oldest enqueued element becomes the top of and can be dequeued first.

The amortized analysis is simple: each enqueued element will be pushed once into , moved once from to , and popped once from . If each enqueue is charged , it can pay for all three constant-cost actions associated with that element. Thus both queue operations have amortized cost.

1.6.2 Union by Smaller Set

Suppose a set data structure supports

in time by moving or relabeling the elements of the smaller set. Starting from singleton sets, each time an element is moved, the size of its containing set at least doubles. An element can therefore be moved at most times before it belongs to the full universe of size .

The total movement over all unions is , and the amortized cost per union is .

1.6.3 Periodic Rebalancing

Some data structures perform occasional global repairs. For example, a binary search tree might insert normally and then rebalance after enough insertions have accumulated. The accounting method handles this by charging each insertion extra credit and saving that credit for the next full rebuild.

The central design question is not whether rebuilding is expensive; it is whether enough cheap operations must occur between rebuilds to pay for it. If a tree of size is rebuilt in time only after insertions have occurred, then charging extra per insertion is enough to pay for the rebuild.

2. Definitions

  • Amortized analysis: A worst-case analysis of the average cost per operation over every valid sequence of operations.
  • Actual cost : The real cost paid by the -th operation.
  • Amortized cost : The artificial cost assigned to the -th operation for analysis.
  • Aggregate analysis: A method that bounds total cost for operations and divides by .
  • Accounting method: A method that overcharges some operations and stores the surplus as credit for later expensive operations.
  • Credit: Stored prepaid work used to pay for future actual cost.
  • Prefix condition: The requirement that total amortized cost is at least total actual cost for every prefix of the sequence.
  • Potential method: A method that represents stored prepaid work by a function of the data-structure state.
  • Potential function : A function assigning stored energy or credit to a data-structure state.
  • State : The data structure after the -th operation.
  • Binary counter: A bit-array representation of an integer where increment may flip trailing bits to and one bit to .
  • Trailing 1s: Consecutive bits at the low-order end of a binary counter.
  • Dynamic array: An array-backed sequence that resizes when capacity becomes insufficient.
  • Capacity : The number of elements that can fit in the currently allocated table.
  • Load factor : The ratio of stored elements to capacity.
  • Hysteresis: Using different thresholds for expansion and contraction to avoid repeated resizing.
  • Queue from two stacks: A FIFO queue implementation that uses one stack for incoming elements and one stack for outgoing elements.
  • Union by smaller set: A union strategy that always moves or relabels elements of the smaller set.
  • Periodic rebalancing: Occasional global rebuilding paid for by credit accumulated during ordinary operations.

3. Formulas

  • Aggregate amortized cost:
  • Accounting prefix condition: for every
  • Potential amortized cost:
  • Potential validity condition: for every
  • Binary-counter aggregate flips:
  • Stack potential:
  • Binary-counter potential:
  • Expansion-only dynamic-array potential:
  • Expansion-contraction table potential:
  • Union-by-smaller-set movement bound: moves per element

4. Practice

4.1. Analyze Multi-Pop Stack by Aggregate Analysis (Lecture 14, Example 1)

Using aggregate analysis, analyze the total running time of a sequence of operations , , and on an initially empty stack.

Click to see the solution

Key Concept: A popped element must previously have been pushed, and each pushed element can be popped at most once.

First consider the loose bound. In one operation, may remove many elements. If the stack has elements, one such operation may cost . Treating every one of the operations as if it could independently cost gives

This bound is valid but not tight.

For the tight aggregate analysis, count element movements instead:

  1. Each inserts one element and costs .
  2. Each element inserted by a push can be removed only once.
  3. A removal may happen through or as one of the removals inside .
  4. Since the sequence has at most pushes, at most elements can ever be removed.

Therefore the total cost of all pushes is at most , and the total cost of all removals is at most . Hence

Dividing by the number of operations gives

Answer: Any sequence of stack operations costs total, so each operation has amortized cost.

4.2. Analyze Binary Counter by Aggregate Analysis (Lecture 14, Example 2)

Use aggregate analysis to analyze the cost of incrementing a binary counter stored as a bit array.

Click to see the solution

Key Concept: Bit flips only once every increments, so high-order bits are cheap over a long sequence.

Let be the least significant bit. During increments:

  • bit flips on every increment, so at most times;
  • bit flips every increments, so at most times;
  • bit flips every increments, so at most times;
  • in general, bit flips at most times.

Thus the total number of flips is at most

The geometric series satisfies

Therefore

The amortized cost per increment is

Answer: A sequence of increments flips fewer than bits, so one increment costs amortized time.

4.3. Analyze Multi-Pop Stack by the Accounting Method (Lecture 14, Example 3)

Analyze a sequence of operations , , and on an initially empty stack using the accounting method.

Click to see the solution

Key Concept: Store one credit on each pushed element, and use that credit when the element is removed.

Assign amortized costs as follows:

Operation Actual cost Amortized cost
if nonempty
number of removed elements

When happens, the operation pays:

The first unit pays for the actual push. The second unit is stored as credit on the new stack element.

Now consider any future removal. If an element is removed by , its own stored credit pays the actual cost . If an element is removed as part of , the same argument applies: each removed element carries one credit, and that credit pays for removing that element.

The credit balance can never become negative because the data structure never removes an element that was not previously pushed. Each removal consumes the credit of exactly one existing element.

Thus every operation has amortized cost at most , which is .

Answer: Charge cost and charge both pop operations cost ; the stored credit on pushed elements pays for all removals, giving amortized cost.

4.4. Analyze Binary Counter by the Accounting Method (Lecture 14, Example 4)

Use the accounting method to analyze a sequence of INCREMENT operations on a binary counter stored as a bit array.

Click to see the solution

Key Concept: A bit that is set to stores credit for the later moment when it is reset to .

During one increment, some number of trailing bits change to , and then at most one bit changes to .

Use this charging scheme:

  • charge for a flip ;
  • charge for a flip .

When a bit flips from to , one unit pays for the actual flip and one unit is stored as credit on that bit. Later, if that bit flips from to , the stored credit pays for the reset.

Now check a whole increment. It may reset trailing bits, but each of those bits already contains one stored credit. The increment then sets at most one bit to , and this costs amortized .

So the amortized cost of one increment is at most

The credit balance is always nonnegative because only bits currently equal to may be reset, and every such bit received credit when it became .

Answer: Charge for the single flip and let stored credits pay for all flips; each increment costs amortized time.

4.5. Analyze Multi-Pop Stack by the Potential Method (Lecture 14, Example 5)

Analyze a sequence of operations , , and on an initially empty stack using the potential method.

Click to see the solution

Key Concept: The number of elements in the stack is exactly the amount of prepaid removal work.

Let

The stack starts empty, so . The potential is never negative, so the potential method is valid.

For , suppose the stack had elements before the operation. The actual cost is , and the stack has elements afterward. Therefore

For , suppose the stack had elements before the operation. The actual cost is , and the stack has elements afterward. Therefore

For , let

be the number of elements actually removed. The actual cost is , and the potential decreases from to . Hence

All three amortized costs are at most .

Answer: With , push costs amortized and both removal operations cost amortized, so every operation is amortized.

4.6. Analyze Binary Counter by the Potential Method (Lecture 14, Example 6)

Use the potential method to analyze INCREMENT on a binary counter stored as a bit array.

Click to see the solution

Key Concept: The bits store exactly the potential needed to pay for future carry propagation.

Let

The initial all-zero counter has potential , and the number of bits is never negative, so the potential function is valid.

Suppose an increment changes trailing bits into bits. If the counter has an available higher bit, the operation then changes one bit into . The actual number of flips is

Let the old number of bits be . After the operation, old bits disappear and one new bit appears, so the new number of bits is

The potential change is therefore

Now compute the amortized cost:

If the counter overflows because all bits are , then the operation flips bits to and does not create a new bit. The actual cost is , the potential change is , and the amortized cost is . This is still bounded by .

Answer: With potential equal to the number of bits, each increment has amortized cost at most , hence .

4.7. Analyze Dynamic Array Expansion (Lecture 14, Example 7)

Consider a dynamic array that supports AddLast. When the array is full, the capacity doubles and all existing elements are copied. Analyze AddLast using the potential method.

Click to see the solution

Key Concept: Ordinary appends build up potential that pays for the next resize.

Let be the number of elements and be the capacity after an operation. Use

Assume the table is initialized and resized so that the potential is nonnegative in the states under consideration. This is the standard expansion-only setting where the table is at least half full after the initial small cases.

There are two cases.

Case 1: no resize. Before the operation, the table has elements and capacity , with . The operation appends one element, so the actual cost is . The new state has elements and the same capacity :

Thus

Case 2: resize. Before the operation, the table is full: . To append, we copy old elements and insert the new one, so the actual cost is . The new capacity is , and the new number of elements is .

The new potential is

The old potential is

Therefore

Both cases have amortized cost .

Answer: With , every AddLast has amortized cost , so expansion-only dynamic arrays support append in amortized time.

4.8. Implement a Queue with Two Stacks (Lecture 14, Example 8)

Implement a queue using two stacks so that Enqueue and Dequeue have amortized cost. Prove the bound using the accounting method.

Click to see the solution

Key Concept: Each element is pushed onto the input stack once, transferred once, and popped from the output stack once.

Use two stacks:

  • receives newly enqueued elements;
  • supplies elements for dequeue.

The operations are:

ENQUEUE(x)
1  R.push(x)

DEQUEUE()
1  if F is empty
2      while R is not empty
3          F.push(R.pop())
4  return F.pop()

The transfer reverses the order of . The element that has waited longest in becomes the top of , so dequeue order is FIFO.

Now assign amortized costs:

Operation part Actual cost Amortized charge
push into during Enqueue
move one element paid by stored credit
pop from during Dequeue

A single enqueue is charged . One unit pays for the immediate push into . The remaining two units are stored on that element. Later, if the element is transferred, moving it from to costs two primitive stack operations: one pop from and one push into . The stored two credits pay for that transfer.

Finally, the actual pop from is charged directly to the dequeue operation with amortized cost .

Each element is transferred at most once, because after it moves from to , it never returns to . Therefore the stored credits are sufficient.

Answer: Use one input stack and one output stack; charge enqueue and dequeue . The transfer cost is prepaid by enqueue credits, so both operations are amortized.

4.9. Analyze Dynamic Table with Expansion and Contraction (Lecture 14, Example 9)

Consider a dynamic array supporting AddLast and RemoveLast. When full, the table doubles in size; when the number of elements drops below one quarter of the capacity, the table halves in size. Analyze the operations using the potential method.

Click to see the solution

Key Concept: The potential must pay for both copying during expansion and copying during contraction.

Let be the number of stored elements and be the table capacity. Use the potential

This function is always nonnegative in the allowed range. It is zero at , grows as the table becomes full, and also grows as the table becomes too empty.

For ordinary operations that do not resize, is unchanged and changes by . In either linear branch of the potential function, the potential changes by at most in absolute value. Since the actual operation cost is , the amortized cost is bounded by a constant.

Now check expansion. Just before expansion, . The old potential is

The operation copies old elements and inserts one new element, so the actual cost is . After expansion, the new number of elements is and the new capacity is . The new load is slightly above one half, so

Thus

Now check contraction. Contraction happens after a removal makes the size drop below . Let the size after removal be . The old capacity is , and the new capacity is . At the threshold, is about , so the cost of copying the remaining elements is .

Before contraction, the table is in the lower branch, so the potential is approximately

When , this is approximately , which is enough to pay for copying elements. After halving the capacity, the new table is near half full, so the potential returns close to .

Therefore the expensive contraction is paid by the potential accumulated while the table was becoming sparse.

Answer: The piecewise potential above gives constant amortized cost for ordinary operations and pays for both resizing directions, so AddLast and RemoveLast are amortized.

4.10. Analyze Union by Smaller Set (Lecture 14, Example 10)

Consider a data structure storing a universe of elements and supporting in time . Initially all sets are singletons. Show amortized cost per union, where is the total number of elements.

Click to see the solution

Key Concept: Whenever an element is moved, the size of its containing set at least doubles.

Implement union by moving or relabeling every element of the smaller set into the larger set. The cost of

is proportional to

Track one fixed element . Initially belongs to a singleton set of size . The only time pays cost is when its current set is the smaller set in a union and therefore gets moved.

Suppose is in a set of size and gets moved into another set. Since its set is the smaller one, the other set has size at least . After the union, the new set containing has size at least

So every time is moved, the size of its set at least doubles:

The set size can never exceed , so can be moved at most

times.

There are elements, so the total number of element moves over the entire sequence is

Since there can be at most successful unions starting from singleton sets, the amortized cost per successful union is

The same reasoning can be expressed as a potential argument by assigning each element remaining movement potential proportional to the number of future doublings still possible.

Answer: Moving the smaller set makes each element move at most times, so the amortized cost of Union is .

4.11. Analyze Periodic Rebalancing of a Binary Search Tree (Lecture 14, Example 11)

Consider a binary search tree supporting Insert(x). After every insertions, where is the current height of the tree, perform a full rebalance in time, where is the number of keys in the tree. Analyze Insert using the accounting method and show amortized cost per insertion.

Click to see the solution

Key Concept: Each insertion deposits credit toward the next rebuild, and rebuilding restores logarithmic height.

After a full rebalance, a binary search tree with keys has height

Let this height be . The rule says that after every insertions, the tree is rebuilt. A normal insertion in a tree of height costs , and because immediately after rebalancing, the search-and-link part of insertion is during the phase up to the next rebuild.

Now pay for the rebuild. A full rebalance costs . The lecture statement says to deposit credit on each insertion toward the future rebalance. To obtain amortized insertion cost, each insertion can deposit credit.

Over a phase of sufficiently many insertions, this accumulates enough credit to pay for global rebuilding. The intended amortized-accounting picture is:

  1. Each insertion pays its own search and link cost, .
  2. Each insertion also deposits credit.
  3. The saved credits are spent when the next full rebalance occurs.

Thus every insertion is charged

amortized cost.

One subtle point is that the exact trigger rule must guarantee enough insertions between rebuilds to fund an rebuild. In standard periodic rebuilding schemes, this is done by rebuilding after a linear-size batch of updates or by using a more precise balance invariant. Under the lecture’s intended accounting assumption that the deposited credits cover each scheduled rebuild, the amortized insertion bound is .

Answer: Charge each insertion for its ordinary work and another as rebuild credit; the accumulated credit pays for full rebalancing, giving amortized insertion cost.